﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

//杨辉三角
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    vector<vector<int>> tri(n, vector<int>(n + 1));

    tri[0][1] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            tri[i][j] = tri[i - 1][j] + tri[i - 1][j - 1];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            printf("%5d", tri[i][j + 1]);
        }
        cout << endl;
    }

    return 0;
}


//大数加法
class Solution {
public:
    string solve(string s, string t) {
        stack<char> st;
        string longStr = s;
        string shortStr = t;
        if (longStr.size() < shortStr.size())
        {
            longStr = t;
            shortStr = s;
        }

        int carry = 0;
        while (!shortStr.empty())
        {
            int shortNum = shortStr.back() - '0';
            int longNum = longStr.back() - '0';
            int sum = shortNum + longNum + carry;
            if (sum / 10)
            {
                carry = 1;
                sum = sum % 10;
            }
            else
            {
                carry = 0;
            }
            st.push(sum + '0');

            shortStr.pop_back();
            longStr.pop_back();
        }

        while (!longStr.empty())
        {
            int sum = longStr.back() - '0' + carry;
            if (sum / 10)
            {
                carry = 1;
                sum = sum % 10;
            }
            else
            {
                carry = 0;
            }
            st.push(sum + '0');

            longStr.pop_back();
        }

        if (carry != 0)
        {
            st.push('1');
        }

        string res;
        while (!st.empty())
        {
            char tmp = st.top();
            res += tmp;
            st.pop();
        }

        return res;
    }
};


//链表相加
class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        queue<int> q;
        stack<int> st1;
        stack<int> st2;

        ListNode* cur1 = head1;
        while (cur1 != nullptr)
        {
            st1.push(cur1->val);
            cur1 = cur1->next;
        }

        ListNode* cur2 = head2;
        while (cur2 != nullptr)
        {
            st2.push(cur2->val);
            cur2 = cur2->next;
        }

        int carry = 0;
        while (!st1.empty() && !st2.empty())
        {
            int num1 = st1.top();
            int num2 = st2.top();
            int sum = num1 + num2 + carry;
            if (sum / 10)
            {
                carry = 1;
                sum = sum % 10;
            }
            else
            {
                carry = 0;
            }
            st1.pop();
            st2.pop();
            q.push(sum);
        }

        while (!st1.empty())
        {
            int sum = st1.top() + carry;
            if (sum / 10)
            {
                carry = 1;
                sum = sum % 10;
            }
            else
            {
                carry = 0;
            }
            st1.pop();

            q.push(sum);
        }

        while (!st2.empty())
        {
            int sum = st2.top() + carry;
            if (sum / 10)
            {
                carry = 1;
                sum = sum % 10;
            }
            else
            {
                carry = 0;
            }
            st2.pop();

            q.push(sum);
        }

        if (carry != 0)
        {
            q.push(1);
        }

        ListNode* head = nullptr;
        while (!q.empty())
        {
            int tmp = q.front();
            if (head == nullptr)
            {
                head = new ListNode(tmp);
                head->next = nullptr;
            }
            else
            {
                auto newnode = new ListNode(tmp);
                newnode->next = head;
                head = newnode;
            }

            q.pop();
        }

        return head;
    }
};


//单词搜索
class Solution {
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    bool check[101][101];
    string word;
public:
    bool exist(vector<string>& board, string _word) {
        word = _word;
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == word[0])
                {
                    check[i][j] = true;
                    if (dfs(board, i, j, 1)) return true;
                    check[i][j] = false;
                }
            }
        }
        return false;
    }

    bool dfs(vector<string>& board, int i, int j, int pos)
    {
        if (pos == word.size())
        {
            return true;
        }

        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];

            if (x >= 0 && x < board.size() && j >= 0 && j < board[0].size() && !check[x][y] && board[x][y] == word[pos])
            {
                check[x][y] = true;
                if (dfs(board, x, y, pos + 1)) return true;
                check[x][y] = false;
            }
        }

        return false;
    }
};

#include <algorithm>

//数组中的最长连续子序列
class Solution {
    void Distinct(const vector<int>& arr, vector<int>& nums)
    {
        if (arr.size() == 1)
        {
            nums.push_back(arr[0]);
            return;
        }

        int left = 0;
        int right = 1;

        while (right < arr.size())
        {
            if (arr[left] != arr[right])
            {
                nums.push_back(arr[left]);
                left = right;
            }
            ++right;
        }

        nums.push_back(arr[left]);

        return;
    }

public:
    int MLS(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        vector<int> nums;
        Distinct(arr, nums);

        int n = nums.size();
        int res = 1;

        vector<int> dp(n, 1);

        for (int i = 1; i < n; i++)
        {
            if (nums[i] == nums[i - 1] + 1)
            {
                dp[i] = dp[i - 1] + 1;
            }
            res = max(res, dp[i]);
        }

        return res;
    }
};

#include <string>

//字母收集
int main() {
    int n = 0;
    int m = 0;
    cin >> n >> m;

    vector<vector<char>> word(n, vector<char>(m));
    /*getchar();*/

    for (int i = 0; i < n; i++)
    {
        string tmp;
        /*getline(cin, tmp);*/
        cin >> tmp;
        for (int j = 0; j < m; j++)
        {
            word[i][j] = tmp[j];
        }
    }

    int grade[26] = { 0 };
    grade['l' - 'a'] = 4;
    grade['o' - 'a'] = 3;
    grade['v' - 'a'] = 2;
    grade['e' - 'a'] = 1;

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < m + 1; j++)
        {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grade[word[i - 1][j - 1] - 'a'];
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}


#include <iostream>
#include <cmath>
#include <string>
using namespace std;
string s;
bool isprim(int n) // 判断 n 是否是质数
{
    if(n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
int main()
{
    cin >> s;
    int hash[26] = { 0 };
    for (auto ch : s)
    {
        hash[ch - 'a']++;
    }
    int minn = 1000, maxn = 0;
    for (int i = 0; i < 26; i++)
    {
        if (hash[i])
        {
            minn = min(minn, hash[i]);
            maxn = max(maxn, hash[i]);
        }
    }
    if (isprim(maxn - minn))
    {
        cout << "Lucky Word" << endl;
        cout << maxn - minn << endl;
    }
    else
    {
        cout << "No Answer" << endl;
        cout << 0 << endl;
    }
    return 0;
}


class Solution
{
public:
    bool hostschedule(vector<vector<int> >& schedule)
    {
        sort(schedule.begin(), schedule.end());
        for (int i = 1; i < schedule.size(); i++)
        {
            if (schedule[i][0] < schedule[i - 1][1]) return false;
        }
        return true;
    }
};


#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m;
int x1, y1, x2, y2;
char arr[N][N];
int dist[N][N]; // [i, j] 位置是否已经搜索过，以及到达 [i, j] 位置的最短距离
int bfs()
{
    if (arr[x2][y2] == '*') return -1;
    memset(dist, -1, sizeof dist); // 表?还没开始搜索
    queue<pair<int, int>> q;
    q.push({ x1, y1 });
    dist[x1][y1] = 0;
    while (q.size())
    {
        auto [a, b] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 1 && x <= n && y >= 0 && y <= m && arr[x][y] == '.' &&
                dist[x][y] == -1)
            {
                q.push({ x, y });
                dist[x][y] = dist[a][b] + 1;
                if (x == x2 && y == y2) return dist[x2][y2];
            }
        }
    }
    return -1;
}
int main()
{
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}


#include <iostream>
#include <queue>
using namespace std;
int n, k;
int main()
{
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        heap.push(x);
    }
    int sum = 0, count = 0;
    while (true)
    {
        int t = heap.top();
        heap.pop();
        sum += t;
        heap.push(t * 2);
        count++;
        if (sum > k)
        {
            cout << count - 1 << endl;
            break;
        }
    }
    return 0;
}


//合并k个已排序的链表
class Solution
{
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // ⼩根堆
        for (auto head : lists){
            if (head != nullptr)
            {
            heap.push(head);
            }
        }
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (heap.size())
        {
            ListNode* t = heap.top();
            heap.pop();
            prev = prev->next = t;
            if (t->next != nullptr)
            {
                heap.push(t->next);
            }
        }
        return ret->next;
    }
};